#define _CRT_SECURE_NO_WARNINGS 1
#include <string.h>
#include<stdlib.h>
#include <math.h>
#include<stdio.h>


//int main()
//{
//	char arr[100000] = "0";
//	scanf("%s", arr);
//	int n = strlen(arr);
//	int s = 0,d=0,x=0,y=0,v=0,b=0;
//	int i = 0;
//	for (i = 0; i < n; i++)
//	{
//		if (arr[i] == 'a')
//		{
//			s++;
//		}
//		else if (arr[i] == 'e')
//		{
//			d++;
//			
//		}
//		else if (arr[i] == 'i')
//		{
//			x++;
//			
//		}
//		else if (arr[i] == 'o')
//		{
//			v++;
//			
//		}
//		else if (arr[i] == 'u')
//		{
//			b++;
//			
//		}
//	}
//	if (s == 0)
//	{
//		return 0;
//	}
//	for (i = 1; i <= s; i++)
//	{
//		printf("a");
//	}
//	for (i = 1; i <= d; i++)
//	{
//		printf("e");
//	}
//	for (i = 1; i <= x; i++)
//	{
//		printf("i");
//	}
//	for (i = 1; i <= v; i++)
//	{
//		printf("o");
//	}
//	for (i = 1; i <= b; i++)
//	{
//		printf("u");
//	}
//	return 0;
//}




//#include <math.h>
//#include<stdio.h>
//int i = 0, s = 0, z = 0, t = 0;
//void NI(char c)
//{
//	/*char c='0';*/
//	//int i = 0, s = 0, z = 0, t = 0;
//		if (c <= 'z'&&c >= 'a') 
//		{
//			i++;
//		}
//		else if (c >= 'A'&&c <= 'Z')
//		{
//			i++;
//		}
//		else if (c >= '0'&&c <= '9')
//		{
//			s++;
//		}
//		else if (c == ' ')
//		{
//			t++;
//		}
//		else
//		{
//			z++;
//		}
//	
//	/*printf("%d %d %d %d", i, s, t, z);*/
//}
//int main()
//{
//	char arr[1000]="0";
//	gets_s(arr);
//	int d=strlen(arr)-1;
//	int f = 0;
//	for (f= 0; f <= d; f++)
//	{
//		NI(arr[f]);
//	}
//	printf("%d %d %d %d", i, s, t, z);
//	return 0;
//}


//#include <stdio.h>
//#include <string.h>
//int s = 0, x = 0, t = 0, v = 0;
//
//void MMM(char d) {
//	if (d >= 'A' && d <= 'Z') {
//		s++;
//	}
//	else if (d >= 'a' && d <= 'z') {
//		s++;
//	}
//	else if (d >= '0' && d <= '9') {
//		x++;
//	}
//	else if (d == ' ') {
//		t++;
//	}
//	else {
//		v++;
//	}
//
//}
//
//int main(void) {
//	char c[100] = "0";
//	gets_s(c);
//	int d = strlen(c) - 1;
//	for (int i = 0; i <= d; i++) {
//		MMM(c[i]);
//	}
//	printf("%d %d %d %d", s, x, t, v);
//	return 0;
//}



//#define swap(a,b,z){z=a,a=b,b=z;}
//int main()
//{
//	int a, b,z;
//	scanf("%d %d", &a, &b);
//	swap(a, b,z);
//	printf("%d %d", a, b);
//	return 0;
//}


//#define yu(a,b){a=a%b;}
//int main()
//{
//	int a, b;
//	scanf("%d %d", &a, &b);
//	yu(a, b);
//	printf("%d", a);
//	return 0;
//}



//#define mi(a,b,c,s){s=(a+b+c)/2.0;}
//#define ma(s,area){area=sqrt(s*(s-a)*(s-b)*(s-c));}
//int main()
//{
//	double a, b, c;
//	scanf("%lf %lf %lf", &a, &b, &c);
//	double s;
//    double area;
//	mi(a, b, c, s);
//	ma(s, area);
//	printf("%.3lf", area);
//	return 0;
//}

//#include <stdio.h>
//#define LEAP_YEAR(l)if (l % 4 != 0 && l % 100 != 0){printf ("L");}else if (l%400==0){printf ("L");}else {printf ("N");}
//int main()
//{
//	int year;
//	scanf("%d", &year);
//	LEAP_YEAR(year);
//	return 0;
//}

	
//int main()
//{
//	float d=0.0;
//	scanf("%f", &d);
//	printf("%6.2f\n", d);
//	printf("%6.2f %6.2f\n", d,d);
//	printf("%6.2f %6.2f %6.2f\n", d,d,d);
//	return 0;
//}

//void MAX(int a, int b, int c)
//{
//	if (a > b) { a = a; }
//	else { a = b; }if (a > c) { a = a; }
//	else { a = c; }
//}
//
//
//#define max(a,b,c)if (a>b){a=a;}else {a=b;}if (a>c){a=a;}else{a=c;}
//int main()
//{
//	float a, b, c;
//	scanf("%f %f %f", &a, &b, &c);
//	max(a,b,c);
//	printf("%.3f\n", a);
//	MAX(a, b, c);
//	printf("%.3f", a);
//	return 0;
//}


//int main()
//{
//	char arr [100000000];
//	gets_s(arr);
//	int d = strlen(arr) - 1;
//	int i = 0;
//	for (i = 0; i <= d; i++)
//	{
//		if (arr[i] == ' ')
//		{
//			continue;
//		}
//		if (arr[i]>='A'&&arr[i]<='Y')
//		{
//			arr[i] = arr[i] + 1;
//		}
//		else if (arr[i] == 'z')
//		{
//			arr[i] = 'a';
//		}
//		else if (arr[i] == 'Z')
//		{
//			arr[i] = 'A';
//		}
//		else if (arr[i] >= 'a'&&arr[i] <= 'y')
//		{
//			arr[i] = arr[i] + 1;
//		}
//	}
//	printf("%s", arr);
//	return 0;
//}


//void MIN(int a, int b, int c)
//{
//
//
//
//}
//
//
//
//
//
//int main()
//{
//	int a, b, c;
//	scanf("%d %d %d", &a, &b, &c);
//	MIN(a, b, c);
//	return 0;
//}




//#include<stdio.h>
//int main()
//{
//	int num[100][100] ;
//	int r, x, y, i, j, d;
//	for (i = 0; i < 21; i++)
//	{
//		for (j = 0; j < 21; j++)
//		{
//			num[i][j] = 0;
//		}
//		
//	}
//	scanf("%d %d %d", &r, &x, &y);
//	for (i = 0; i < 21; i++)
//	{
//		for (j = 0; j < 21; j++)
//		{
//			d = (x - i)*(x - i) + (y - j)*(y - j);
//				if (d <= r * r)
//				{
//					num[i][j] = 1;
//				}
//		}
//	}
//	for (i = 0; i < 21; i++)
//	{
//		for (j = 0; j < 21; j++)
//		{
//			printf("%d ", num[i][j]);
//		}
//		printf("\n");
//	}
//	return 0;
//}


//int sum = 0;
//int PING(int x)
//{
//	if (x >= 2)
//	{
//		x = x - 2;
//		sum++;
//		PING(x);
//	}
//	return sum;
//}
//int main()
//{
//	int a = 1;
//	
//	while (a)
//	{
//		sum = 0;
//		scanf("%d", &a);
//			PING(a);
//			if (a == 0)
//			{
//				return 0;
//			}
//   printf("%d\n", sum);
//	}
//	
//	return 0;
//}



//int main()
//{
//	long a ,b, n,d,c;
//	scanf("%d %d %d", &a, &b, &n);
//	d = b - a;
//	c = a+ (n- 1)*d;
//	printf("%d", c);
//	return 0;
//}

//int main() {
//	int a = 1;
//	int b = 4;
//	int d = b - a;
//	int n = 0;
//	scanf("%d %d %d", &a, &b, &n);
//	int f = 0;
//	f = a + (n - 1) * d;
//	printf("%d", f);
//
//}



//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int i = 0;
//	int j = 0;
//	int d = 0;
//	for (i = 1; i <= n; i++)
//	{
//		for (j = 0;j<n-i; j++)
//		{
//			printf(" ");
//		}
//		for (d = 0; d < 2*i-1; d++)
//		{
//			printf("*");
//		}
//		printf("\n");
//	}
//	for (i = n-1; i >= 1; i--)
//	{
//		for (j = 0; j < n - i; j++)
//		{
//			printf(" ");
//		}
//		for (d = 0; d < 2 * i - 1; d++)
//		{
//			printf("*");
//		}
//		printf("\n");
//	}
//
//	return 0;
//}



//int main()
//{
//	int num[100000];
//	int n,i,t=0,s,f=0;
//	int sc[10000];
//	scanf("%d", &n);
//	for (i = 0; i < n; i++)
//	{
//		scanf("%d", &num[i]);
//	}
//	for (i = 0; i < n; i++)
//	{
//		for (int j = 0; j <= n - 1 - i; j++)
//		{
//			if (num[j] < num[j+1] )
//			{
//				s = num[j];
//				num[j] = num[j + 1];
//				num[j + 1] = s;
//			}
//		}
//	}
//	for (i = 0; i < n; i++)
//	{
//		if (num[i] < 0)
//		{
//			t++;
//		}
//		else if (num[i] > 0)
//		{
//			sc[i - t] = num[i];
//			f++;
//		}
//	}
//	for (i = 0; i < f; i++)
//	{
//		printf("%d ", sc[i]);
//	}
//	return 0;
//}



//struct student
//{
//	char name[100];
//	int  id;
//	int s1;
//};
//int main()
//{
//	int n,m;
//	scanf("%d", &n);
//	int i = 0;
//	struct student stu[1000];
//	for (i = 0; i < n; i++)
//	{
//		scanf("%d %s %d", &stu[i].id, stu[i].name, &stu[i].s1);
//	}
//	scanf("%d", &m);
//	int x, y;
//	for (i = 0; i < m; i++)
//	{
//		scanf("%d %d", &x, &y);
//		for (int j = 0; j < n; j++)
//		{
//			if (stu[j].id == x)
//			{
//				stu[j].s1 = y;
//			}
//		}
//	}
//	for (i = 0; i < n; i++)
//	{
//		printf("%d %s %d\n", stu[i].id, stu[i].name, stu[i].s1);
//	}
//	return 0;
//}


//#include <stdio.h>
//struct st{
//	int a;
//	char b[100];
//	int c;
//} d[100];
//
//int main() {
//	int n;
//	scanf("%d", &n);
//	for (int i = 0; i < n; i++) {
//		scanf("%d%s%d", &d[i].a, &d[i].b, &d[i].c);
//	}
//	int m, a, c;
//	scanf("%d", &m);
//	for (int i = 0; i < m; i++) {
//		scanf("%d %d", &a, &c);
//		for (int j = 0; j < n; j++) {
//			if (d[j].a == a) {
//				d[j].c = c;
//			}
//		}
//	}
//	for (int i = 0; i < n; i++) {
//		printf("%d %s %d\n", d[i].a, d[i].b, d[i].c);
//	}
//	return 0;
//}


//struct student 
//{
//	char name[100];
//	int s1;
//};
//int main()
//{
//	int i = 0,n,j=0,x=0;
//	char c[1000];
//	scanf("%d", &n);
//	struct student stu[1000];
//	for (i = 0; i < n; i++)
//	{
//		scanf("%s %d", stu[i].name, &stu[i].s1);
//	}
//	for (i = 0; i < n; i++)
//	{
//		for (j = 0; j < n - i; j++)
//		{
//			if (stu[j].s1 < stu[j + 1].s1)
//			{
//				struct student t = stu[j];
//				stu[j] = stu[j + 1];
//				stu[j + 1] = t;
//			}
//		}
//	}
//	for (i = 0; i < n; i++)
//	{
//		printf("%s %d\n", stu[i].name, stu[i].s1);
//	}
//	return 0;
//}


//int main()
//{
//	int a = 111,t=0;
//	while (a)
//	{
//		a = a / 10;
//		t++;
//	}
//	printf("%d", t);
//	return 0;
//}



//#include <stdio.h>
//#include <math.h>
//
//int main(void) 
//{
//	int a, n, i = 0, t=0, j=0, h=0, k=0, v = 0, o = 0;
//	scanf("%d %d", &a, &n);
//	int num[100000];
//	for (i = a; i <= n; i++)
//	{
//		k = 0;
//		h = i;
//		t = 0;
//		while (h) {
//			h = h / 10;
//			t++;
//		}
//		h = i;
//		for (j = 0; j < t; j++) {
//			num[j] = h % 10;
//			h = h / 10;
//		}
//		int u = t - 1;
//		for (int x =0; x < t; x++) {
//			k = num[x] * pow(10,u-x) + k;
//		}
//		if (k == i) 
//		{
//			for (int s = 2; s <i; s++)
//			{
//				v = 0;
//				if (i % s == 0) 
//				{
//					v++;
//					break;
//				}
//			}
//			if (v == 0)
//			{
//				o++;
//			}
//
//		}
//	}
//	
//	printf("%d", o);
//	return 0;
//}
/*if (a==0&&n==0)
	{
		o = 0;
	}
	if (a == 1)
	{
		o = o - 1;
	}
	if (a == 0&&n!=0)
	{
		o-= 2;
	}*/


//#include <stdio.h>
//int main(void) {
//	int i, j, k, t = 0;
//	int num[5][5];
//	int b[5][5];
//	for (i = 0; i < 5; i++) {
//		for (j = 0; j < 5; j++) {
//			scanf("%d", &num[i][j]);
//			b[i][j] = num[i][j];
//		}
//	}
//	for (i = 0; i < 5; i++) {
//		for (k = 0; k < 5 - i; k++) {
//			if (b[i][k] < b[i][k + 1]) {
//				t = b[i][k];
//				b[i][k] = b[i][k + 1];
//				b[i][k + 1] = t;
//			}
//		}
//	}
//	for (i = 0; i < 5; i++) {
//		for (j = 0; j < 5; j++) {
//			printf("%d ", b[i][j]);
//		}
//		printf("\n");
//	}
//	return 0;
//}
